// copyright:no copyright,use it if you like
// license boilerplate:BSD 3-Clause
// filename:Balance Tree.h
// author:Tempest(https://gitee.com/Tempest56890)
// date:2021-11-23
// brief:implement the function of Splay Tree

#ifndef __TEMPEST_BALANCETREE__
#define __TEMPEST_BALANCETREE__

#include <iostream>
#include <algorithm>
#include <vector>

template <typename Comparable>
// implement the funciton of SplayTree.
// example:
//    (Temporarily omitted.)
class SplayTree {
public:
    // SplayT constructor.
    SplayTree ()
    :root(nullptr) {};
    // deep copy to construct a SplayT.
    SplayTree(const SplayTree & rhs )
    :root(nullptr) {
        root=clone(rhs.root);
    };
    // SplayT destructor.
    ~SplayTree () {
        makeEmpty();
    };
    // transmit the root pointer to private function of
    // same name,and give a minimum by recursion.
    const Comparable & findMin() const {
        return findMin(root)->element;
    };
    // transmit the root pointer to private function of
    // same name,and give a maximum by recursion.
    const Comparable & findMax() const {
        return findMax(root)->element;
    };
    // transmit the root pointer to private function of
    // same name,and give a bool result by recursion.
    bool contains(const Comparable & x) const {
        return contains(x,root);
    };
    // judge if the SplayT is empty.
    bool isEmpty() const {
        if (root==nullptr)
            return true;
        return false;
    };
    // transmit the root pointer to private function of
    // same name,and print tree by recursion.
    void printTree() const {
        if (isEmpty())
            std::cout<<"It's empty."<<std::endl;
        else
            printTree(root,0);
    };
    // transmit the root pointer to private function of
    // same name,and delete tree's node by recursion.
    void makeEmpty() {
        makeEmpty(root);
    };
    // transmit the root pointer to private function of
    // same name,and insert x according to its relative
    // size by recursion.
    void insert(Comparable & x) {
        insert(x,root);
    };
    // transmit the root pointer to private function of
    // same name,find and remove x according to its relative
    // size by recursion.
    void remove(const Comparable & x) {
        remove(x,root);
    };
    // overloads operator = for class object to deep copy.
    // return:a const pointer to the current object
    // the reference parameter rhs has to be maintained and
    // released when function ends.
    // the parameter can be a null pointer.
    const SplayTree & operator=(const SplayTree & rhs) {
        if (this!=&rhs) {
            makeEmpty();
            root=clone(rhs.root);
        }
        return *this;
    };
    
private:
    // construct a SplayTree struct.
    // provide a funciton to initialize a node.
    struct SplayNode {
        Comparable element;
        SplayNode *left;
        SplayNode *right;
        SplayNode(const Comparable & theElement,SplayNode*lt,SplayNode*rt)
        : element(theElement),left(lt),right(rt) {}
    };
    SplayNode * root;
    //
    void RotateWithLeftChild(SplayNode * & t) {
        SplayNode *t1=t->left;
        if (t1!=nullptr) {
            t->left=t1->right;
            t1->right=t;
            t=t1;}
        else
            ;
    };
    //
    void RotateWithRightChild(SplayNode * & t) {
        SplayNode *t1=t->right;
        if (t1!=nullptr) {
            t->right=t1->left;
            t1->left=t;
            t=t1;}
        else
            ;
    };
    //
    void DoubleWithLeftChild(SplayNode * & t) {
        RotateWithRightChild(t->left);
        RotateWithLeftChild(t);
    };
    //
    void DoubleWithRightChild(SplayNode * & t) {
        RotateWithLeftChild(t->right);
        RotateWithRightChild(t);
    };
    void RotateLeftLeftChild(SplayNode * & t) {
        RotateWithLeftChild(t);
        RotateWithLeftChild(t);
    }
    void RotateRightRightChild(SplayNode * & t) {
        RotateWithRightChild(t);
        RotateWithRightChild(t);
    }
    // i/o param:x/t
    // function call insert().
    void move(Comparable & x,SplayNode * & t) {
        if (t==nullptr || t->element==x || (t->left==nullptr && t->right==nullptr))
            ;
        else if (t->left!=nullptr && t->left->element==x)
            RotateWithLeftChild(t);
        else if (t->right!=nullptr && t->right->element==x)
            RotateWithRightChild(t);
        else if (t->left!=nullptr && t->left->left!=nullptr && t->left->left->element==x)
            RotateLeftLeftChild(t);
        else if (t->right!=nullptr && t->right->right!=nullptr && t->right->right->element==x)
            RotateRightRightChild(t);
        else if (t->left!=nullptr && t->left->right!=nullptr && t->left->right->element==x)
            DoubleWithLeftChild(t);
        else if (t->right!=nullptr && t->right->left!=nullptr && t->right->left->element==x)
            DoubleWithRightChild(t);
        else if (t->left!=nullptr)
            move(x,t->left);
        else if (t->right!=nullptr)
            move(x,t->right);
        else
            ;
    };
    void Splay(Comparable & x) {
        while (root->element!=x) {
            move(x,root);
        }
    }
    void insert(Comparable & x,SplayNode * & t ) {
        if (t==nullptr) {
            t=new SplayNode(x,nullptr,nullptr);
            Splay(x);
        }
        else if (x<t->element) {
            insert(x,t->left);
        }
        else if (t->element<x) {
            insert(x,t->right);
        }
        else
            ;//Duplicate; do nothing
    };
    // i/o param:x/t
    // function call remove().
    // the oldNode rhs has to be maintained and
    // released when function ends.
    void remove(const Comparable & x,SplayNode * & t) {
        if (t==nullptr) return;
        if (x<t->element) {
            remove(x,t->left);
        }
        else if (t->element<x) {
            remove(x,t->right);
        }
        else if (t->right!=nullptr) {
            t->element=findMin(t->right)->element;
            remove(t->element,t->right);
        }
        else if (t->left!=nullptr) {
            t->element=findMax(t->left)->element;
            remove(t->element,t->left);
        }
        else {
            t=nullptr;
        }
    };
    // i/o param:t
    // function call findMin().
    SplayNode * findMin(SplayNode * t) const {
        if (t==nullptr)
            return nullptr;
        else if (t->left==nullptr) {
            return t;
        }
        return findMin(t->left);
    };
    // i/o param:t
    // function call findMax().
    SplayNode * findMax(SplayNode * t) const {
        if (t!=nullptr)
            while (t->right!=nullptr)
                t=t->right;
        return t;
    };
    // i/o param:x/t
    // function call contains().
    bool contains(const Comparable & x,SplayNode * t) const {
        if (t==nullptr)
            return false;
        else if (x<t->element)
            return contains(x,t->left);
        else if (t->element<x)
            return contains(x,t->right);
        else
            return true;
    };
    // i/o param:t
    // function call makeEmpty().
    void makeEmpty(SplayNode * & t ) {
        if (t!=nullptr) {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t=nullptr;
    };
    // i/o param:t/count(=0)
    // function call insert().
    // a node's depth would embodied the size
    // of space ahead of itself.
    void printTree(SplayNode * t ,int count=0) const {
        int count1=count;
        if (t==nullptr)
            return;
        for(int i=0;i<count1;i++) {
            std::cout<<" ";
        }
        std::cout<<t->element<<std::endl;
        count1=count1+1;
        printTree(t->left,count1);
        printTree(t->right,count1);
    };
    // i/o param:x/t
    // return:a new cloned Splay Tree.
    // function call clone().
    SplayNode * clone(SplayNode * t) const {
        if (t==nullptr)
            return nullptr;
        return new SplayNode(t->element,clone(t->left),clone(t->right),t->height);
    };
};

template <typename Comparable>
// implement the funciton of AVLTree.
// example:
//    (Temporarily omitted.)
class AVLTree {
public:
    // AVLT constructor.
    AVLTree ()
    :root(nullptr) {};
    // deep copy to construct a AVLT.
    AVLTree(const AVLTree & rhs )
    :root(nullptr) {
        root=clone(rhs.root);
    };
    // AVLT destructor.
    ~AVLTree () {
        makeEmpty();
    };
    // transmit the root pointer to private function of
    // same name,and give a minimum by recursion.
    const Comparable & findMin() const {
        return findMin(root)->element;
    };
    // transmit the root pointer to private function of
    // same name,and give a maximum by recursion.
    const Comparable & findMax() const {
        return findMax(root)->element;
    };
    // transmit the root pointer to private function of
    // same name,and give a bool result by recursion.
    bool contains(const Comparable & x) const {
        return contains(x,root);
    };
    // judge if the AVLT is empty.
    bool isEmpty() const {
        if (root==nullptr)
            return true;
        return false;
    };
    // transmit the root pointer to private function of
    // same name,and print BST by recursion.
    void printTree() const {
        if (isEmpty())
            std::cout<<"It's empty."<<std::endl;
        else
            printTree(root,0);
    };
    // transmit the root pointer to private function of
    // same name,and delete BST's node by recursion.
    void makeEmpty() {
        makeEmpty(root);
    };
    // transmit the root pointer to private function of
    // same name,and insert x according to its relative
    // size by recursion.
    void insert(const Comparable & x) {
        insert(x,root);
    };
    // transmit the root pointer to private function of
    // same name,find and remove x according to its relative
    // size by recursion.
    void remove(const Comparable & x) {
        remove(x,root);
    };
    // overloads operator = for class object to deep copy.
    // return:a const pointer to the current object
    // the reference parameter rhs has to be maintained and
    // released when function ends.
    // the parameter can be a null pointer.
    const AVLTree & operator=( const AVLTree & rhs) {
        if (this!=&rhs) {
            makeEmpty();
            root=clone(rhs.root);
        }
        return *this;
    };
    
private:
    // construct a AVLTree struct.
    // provide a funciton to initialize a node.
    struct AVLNode {
        Comparable element;
        AVLNode *left;
        AVLNode *right;
        int height;
        AVLNode(const Comparable & theElement,AVLNode*lt,AVLNode*rt,int h=0)
        : element(theElement),left(lt),right(rt),height(h) {}
    };
    AVLNode *root;
    // i/o param:t
    // provide basic param for AVLTree to judge balance.
    int height(AVLNode * t) const {
        return t==nullptr? -1:t->height;
    };
    //
    void RotateWithLeftChild(AVLNode * & t) {
        AVLNode *t1=t->left;
        t->left=t1->right;
        t1->right=t;
        t->height=std::max(height(t->left),height(t->right))+1;
        t1->height=std::max(height(t1->left),t->height)+1;
        t=t1;
    };
    //
    void RotateWithRightChild(AVLNode * & t) {
        AVLNode *t1=t->right;
        t->right=t1->left;
        t1->left=t;
        t->height=std::max(height(t->right),height(t->left))+1;
        t1->height=std::max(height(t1->right),t->height)+1;
        t=t1;
    };
    //
    void DoubleWithLeftChild(AVLNode * & t) {
        RotateWithRightChild(t->left);
        RotateWithLeftChild(t);
    };
    //
    void DoubleWithRightChild(AVLNode * & t) {
        RotateWithLeftChild(t->right);
        RotateWithRightChild(t);
    };
    // i/o param:x/t
    // function call insert().
    void insert(const Comparable & x,AVLNode * & t ) {
        if (t==nullptr) {
            t=new AVLNode(x,nullptr,nullptr);
        }
        else if (x<t->element) {
            insert(x,t->left);
            if (height(t->left)-height(t->right)==2) {
                if (x<t->left->element)
                    RotateWithLeftChild(t);
                else
                    DoubleWithLeftChild(t);
            }
        }
        else if (t->element<x) {
            insert(x,t->right);
            if (height(t->right)-height(t->left)==2) {
                if (t->right->element<x)
                    RotateWithRightChild(t);
                else
                    DoubleWithRightChild(t);
            }
        }
        else
            ;//Duplicate; do nothing
        t->height=std::max(height(t->left),height(t->right))+1;
    };
    // i/o param:x/t
    // function call remove().
    // the oldNode rhs has to be maintained and
    // released when function ends.
    void remove(const Comparable & x,AVLNode * & t) {
        if (t==nullptr) return;
        if (x<t->element) {
            remove(x,t->left);
            if (height(t->right)-height(t->left)==2) {
                if (height(t->right->right)<height(t->right->left))
                    DoubleWithRightChild(t);
                else
                    RotateWithRightChild(t);
            }
        }
        else if (t->element<x) {
            remove(x,t->right);
            if (height(t->left)-height(t->right)==2) {
                if (height(t->left->right)<height(t->left->left))
                    RotateWithLeftChild(t);
                else
                    DoubleWithLeftChild(t);
            }
        }
        else if (t->left!=nullptr || t->right!=nullptr) {
            if (height(t->left)<height(t->right)) {
                t->element=findMin(t->right)->element;
                remove(t->element,t->right);
            }
            else {
                t->element=findMax(t->left)->element;
                remove(t->element,t->left);
            }
        }
        else {
            t=nullptr;
        }
    };
    // i/o param:t
    // function call findMin().
    AVLNode * findMin(AVLNode*t) const {
        if (t==nullptr)
            return nullptr;
        if (t->left==nullptr)
            return t;
        return findMin(t->left);
    };
    // i/o param:t
    // function call findMax().
    AVLNode * findMax(AVLNode*t) const {
        if (t!=nullptr)
            while (t->right!=nullptr)
                t=t->right;
        return t;
    };
    // i/o param:x/t
    // function call contains().
    bool contains(const Comparable & x,AVLNode *t ) const {
        if (t==nullptr)
            return false;
        else if (x<t->element)
            return contains(x,t->left);
        else if (t->element<x)
            return contains(x,t->right);
        else
            return true;
    };
    // i/o param:t
    // function call makeEmpty().
    void makeEmpty( AVLNode * & t ) {
        if (t!=nullptr) {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t=nullptr;
    };
    // i/o param:t/count(=0)
    // function call insert().
    // a node's depth would embodied the size
    // of space ahead of itself.
    void printTree(AVLNode * t ,int count=0) const {
        int count1=count;
        if (t==nullptr)
            return;
        for(int i=0;i<count1;i++) {
            std::cout<<" ";
        }
        std::cout<<t->element<<std::endl;
        count1=count1+1;
        printTree(t->left,count1);
        printTree(t->right,count1);
    };
    // i/o param:x/t
    // return:a new cloned AVLT.
    // function call clone().
    AVLNode * clone(AVLNode * t) const {
        if (t==nullptr)
            return nullptr;
        return new AVLNode(t->element,clone(t->left),clone(t->right),t->height);
    };
};



#else
#endif
